假設今天有兩支程式都能算出正確答案：第一支程式按下執行後馬上顯示結果，第二支程式卻慢到可以先去泡一碗泡麵，回來後電腦還差點因為記憶體不足而當機。它們的答案雖然一樣，但應該沒有人會想選第二支吧！

寫程式不只是「能不能得到正確答案」，還要考慮「要花多少時間」以及「會用掉多少記憶體」。不然一個網頁或 App 每次操作都要等很久，就算功能做得再完整，使用者可能還是會失去耐心。

那要怎麼判斷一支程式跑得快不快、又會占用多少記憶體呢？這時就輪到兩個聽起來很像特殊技能的名詞登場了：時間複雜度與空間複雜度。

什麼是空間複雜度？

程式執行時會占用電腦的記憶體，只是我們平常很少注意它的變化。先來做個小實驗：把下面的 Python 程式貼進終端機執行，再打開「活動監視器」的記憶體頁面並搜尋 Python，就能看到它占用的記憶體不斷增加。

python3 -c '
import time

memory = []

while True:
    memory.append(bytearray(50 * 1024 * 1024))
    print(f"目前使用約 {len(memory) * 50} MB")
    time.sleep(1)
'

這支程式每秒會增加約 50 MB 的記憶體。觀察幾秒後，記得回到終端機按下 Control + C 停止，不然電腦可能會越來越慢喔！

不過，現代作業系統通常會利用記憶體壓縮或交換空間來減輕影響，所以短時間測試不用太緊張；但這些機制也不是無限的，觀察完還是要記得停止程式。

透過剛才的小實驗，就能更直觀地理解空間複雜度。它描述的就是：當資料量增加時，程式需要的記憶體會如何增加。

在簡單的分析中，可以先把使用的空間分成兩類：

1. 固定空間：不會隨著資料量改變的空間，例如固定數量的變數、常數和程式碼。
2. 變動空間：會隨著資料量改變的空間，例如長度由輸入決定的陣列、動態配置的記憶體，或遞迴產生的多層函式呼叫。

這裡先不用急著算出程式到底用了幾個 bytes，因為不同電腦、編譯器和最佳化方式都可能讓實際結果不同。分析複雜度時，我們比較在意的是：資料變多之後，記憶體使用量會不會跟著成長。

先來看一個簡單的相加例子：

#include <stdio.h>

int func1(int x, int y) {
    return x + y;
}

int main(void) {
    int result = func1(3, 5);
    printf("%d\n", result);

    return 0;
}

這個程式使用了 x、y 和 result 三個整數變數。不管傳入的是 3 和 5，還是其他整數，變數的數量都不會增加，因此需要的記憶體是固定的。

另外，return x + y 是把加總結果傳回去，return 0 則是告訴作業系統程式正常結束。這兩個 return 都沒有宣告新的變數，所以不能把它們分別算成一個新的整數變數。

這個程式沒有使用長度會改變的陣列、動態記憶體配置或遞迴，因此可以簡單整理成：

固定空間：x、y、result 等
隨資料量改變的空間：沒有
空間複雜度：O(1)

O(1) 代表使用的空間是常數等級。它不一定真的只占用一個單位的記憶體，而是表示：不管資料量如何變化，使用的記憶體都不會跟著增加。

再看一個陣列範例

接著來看一個會處理陣列的程式：

#include <stdio.h>

void func2(int x, int ary[], int n) {
    const int k = 10;

    for (int i = 0; i < n; i++) {
        ary[i] = i * x * k;
    }
}

int main(void) {
    int array[10];

    func2(5, array, 10);

    for (int i = 0; i < 10; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");

    return 0;
}

程式先在 main 裡建立一個可以存放 10 個整數的陣列 array，接著把數字 5、陣列 array 和陣列長度 10 傳給 func2。

進入 func2 後，for 迴圈會從陣列的第一個位置開始，一個一個算出結果，再把結果存進陣列。它使用的計算方式如下：

ary[i] = i * x * k;

這裡的 x 是傳進來的 5，k 是固定常數 10。例如當 i 等於 3 時，結果就是 3 × 5 × 10 = 150，所以程式會把 150 放進 ary[3]。

最後會得到以下結果：

0 50 100 150 200 250 300 350 400 450

在這個實際範例中，陣列大小固定為 10，不會隨輸入改變，因此使用的空間仍然可以視為 O(1)。稍後分析時間複雜度時，則會把 n 視為可以改變的資料量。

什麼是 Big O？

前面一直出現 O(1)、O(n)，這個看起來有點神祕的 O 到底是什麼呢？

這些記號都屬於 Big O 表示法。它不是用來表示精確的執行秒數或記憶體 bytes，而是用來描述：當輸入規模 n 越來越大時，時間或空間的成長趨勢。

簡單來說，Big O 就像一種大家都看得懂的共同語言，讓我們可以用同一套標準比較不同演算法的效率。

例如，某個演算法需要執行：

2n + 3

當 n 很大時，真正影響成長速度的是 n。常數 2 和 3 不會改變它與 n 成正比的趨勢，所以會簡化成：

O(n)

因此，使用 Big O 時可以先記住兩個簡單原則：

1. 忽略固定的常數，例如 3n 簡化為 O(n)。
2. 只保留成長最快的部分，例如 n² + n + 5 簡化為 O(n²)。

什麼是時間複雜度？

時間複雜度描述的是：當資料量增加時，演算法需要執行的步驟會如何增加。

它不是直接計算程式跑了幾秒，因為同一支程式在不同電腦上執行，所花的時間可能不一樣。我們通常會觀察主要程式碼需要重複執行幾次。

例如下面這行不管 n 是多少，都只執行一次：

int result = x + y;

因此它的時間複雜度是 O(1)。

再回到 func2 的迴圈：

for (int i = 0; i < n; i++) {
    ary[i] = i * x * k;
}

如果陣列有 n 個元素，迴圈就會執行 n 次。當資料量變成兩倍時，執行次數大致也會變成兩倍，因此時間複雜度是 O(n)。

所以 func2 可以整理成：

時間複雜度：O(n)
額外空間複雜度：O(1)

這也說明了時間複雜度和空間複雜度不一定相同。這個函式處理的資料越多，執行時間會跟著增加；但是它沒有另外建立大小為 n 的陣列，所以額外記憶體不會跟著增加。

常見的時間複雜度

目前先認識幾種常見的 Big O：

它們的成長速度大致可以排列成：

O(1) < O(log n) < O(n) < O(n log n) < O(n²)

在資料量很小時，不同演算法的速度可能感覺不出明顯差異；但當資料量越來越大，複雜度較高的演算法通常會花費更多時間。

例如兩層迴圈都執行 n 次：

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        printf("%d %d\n", i, j);
    }
}

外層執行 n 次，每一次又會讓內層執行 n 次，總執行次數大約是 n × n，所以時間複雜度是 O(n²)。

如何簡單判斷複雜度？

剛開始分析程式時，可以先按照下面的順序思考：

1. 先決定 n 代表什麼：例如陣列長度、學生人數或節點數量。
2. 找出重複執行的部分：特別注意迴圈與遞迴。
3. 觀察執行次數是否隨 n 增加：固定次數通常是 O(1)，走訪全部資料通常是 O(n)。
4. 檢查是否建立額外資料：例如新的陣列、動態記憶體或遞迴呼叫堆疊。
5. 忽略常數與較小的項目：只留下影響成長速度最大的部分。

目前可以先用下面幾句話幫助自己判斷：

沒有隨 n 增加的迴圈：時間通常是 O(1)
走訪一次 n 筆資料：時間通常是 O(n)
兩層迴圈各走訪 n 次：時間通常是 O(n²)
只使用固定數量的額外變數：額外空間通常是 O(1)
另外建立 n 個元素的陣列：額外空間通常是 O(n)

小結

時間複雜度和空間複雜度都是用來觀察演算法效率的工具。時間複雜度關心執行步驟如何增加，空間複雜度則關心記憶體需求如何增加，而 Big O 可以幫助我們忽略硬體速度和實際 bytes 的差異，專注比較演算法的成長趨勢。

今天最重要的是先記住：

O(1)：資料量增加時，使用的時間或空間仍然固定
O(n)：使用的時間或空間會隨資料量成正比增加

之後學習陣列、鏈結串列、堆疊、佇列、樹與各種排序方法時，就可以利用時間複雜度和空間複雜度，比較不同資料結構與演算法各自的優缺點。